package cn.ycl.system.other.study.leetCode.deepFirstSort;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 广度、深度优先遍历
 * 
 *
 */
public class DeepFirstSort2 {
	public static void main(String[] args) {
		TreeNode head=new TreeNode(1);
		TreeNode second=new TreeNode(2);
		TreeNode three=new TreeNode(3);
		TreeNode four=new TreeNode(4);
		TreeNode five=new TreeNode(5);
		TreeNode six=new TreeNode(6);
		TreeNode seven=new TreeNode(7);
		head.right=three;
		head.left=second;
		second.right=five;
		second.left=four;
		three.right=seven;
		three.left=six;
		System.out.print("广度优先遍历结果：");
		new DeepFirstSort2().broadFirstSearch(head);
		System.out.println();
		System.out.print("深度优先遍历结果：");
		new DeepFirstSort2().depthFirstSearch(head);
	}
	
	//广度优先遍历是使用队列实现的
	public void broadFirstSearch(TreeNode nodeHead) {
		Queue<TreeNode> queue = new LinkedList();
		if(nodeHead == null){
			return;
		}
		queue.add(nodeHead);
		while(!queue.isEmpty()){
			TreeNode poll = queue.poll();
			System.out.print(poll.val + " ");
			if(poll.left != null){
				queue.add(poll.left);
			}
			if(poll.right != null){
				queue.add(poll.right);
			}

		}
	}
	
	//深度优先遍历
	public void depthFirstSearch(TreeNode nodeHead) {
		if(nodeHead == null){
			return;
		}
		Stack<TreeNode> stack = new Stack<>();
		stack.push(nodeHead);
		while(!stack.isEmpty()){
			TreeNode pop = stack.pop();
			System.out.print(pop.val + " ");
			if(pop.right != null){
				stack.push(pop.right);
			}
			if(pop.left != null){
				stack.push(pop.left);
			}
		}
		}
 
}